package com.dyz.leetcode._13_binaryTree;

import com.dyz.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class _437_pathSum {
    public int pathSum(TreeNode root, int targetSum) {
        return dfs(root, new ArrayList<>(), targetSum);

    }
    private int dfs(TreeNode node, List<Integer> parentPathSum, int targetSum){
        if(node==null){return 0;}
        int cnt = 0;

        List<Integer> tmp = new ArrayList<>();
        for(int i=0; i<parentPathSum.size(); i++){
            int num = parentPathSum.get(i)+node.val;
            tmp.add(num);
            if(num==targetSum){cnt++;}
        }
        tmp.add(node.val);
        if(node.val==targetSum){cnt++;}

        int leftCnt = dfs(node.left, tmp, targetSum);
        int rightCnt = dfs(node.right, tmp, targetSum);

        return cnt+leftCnt+rightCnt;
    }

    //解法二
    // DFS(前序遍历) + 前缀和
    // O(n)
    private int res = 0;
    public int pathSum1(TreeNode root, int targetSum) {
        Map<Integer, Integer> prefixSumMap = new HashMap<>();
        prefixSumMap.put(0, 1);
        dfs1(root, 0, targetSum, prefixSumMap);
        return res;
    }

    private void dfs1(TreeNode node,
                      int currSum, int targetSum,
                      Map<Integer, Integer> prefixSumMap){
        if (node == null) {return;}

        currSum += node.val;
        res +=prefixSumMap.getOrDefault(currSum - targetSum, 0);
        prefixSumMap.put(currSum, prefixSumMap.getOrDefault(currSum, 0) + 1);

        dfs1(node.left, currSum, targetSum, prefixSumMap);
        dfs1(node.right, currSum, targetSum, prefixSumMap);

        prefixSumMap.put(currSum, prefixSumMap.get(currSum) - 1);
    }
}
